package com.yincb.sort;

import java.util.Arrays;

public class ShellSort {

    /**
     * 希尔排序         { 9, 8, 7, 0, 1, 3, 2 }
     * 希尔排序其实是插入排序的一个改进版
     * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
     * 随着增量逐渐减少，每组的关键词(元素)越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
     * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。
     * 先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，
     * 直至所取的增量=1(  <  …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
     */
    public static void main(String[] args) {

        int a[] = {9, 8, 7, 0, 1, 3, 2, 6, 10, 4};
        int n = a.length; // 10
        int gap = n / 2;
        for (; gap > 0; gap /= 2) {  // 5 2 1 0
            for (int i = gap; i < n; i++) {
                int tem = a[i];
                int j = i - gap;
                for (; j >= 0; j -= gap) {
                    if (a[j] > tem) {
                        a[j + gap] = a[j];
                    } else {
                        break; // 插入排序 其实就是对这个break排序，插入排序对已经排好的数列排数很快，时间复杂度O(n)
                    }
                }
                a[j + gap] = tem;
            }
            System.out.println(gap+"结果为：" + Arrays.toString(a));
        }
    }


}


